package main

type Node struct {
	key   int
	val   int
	count int
	next  *Node
	prev  *Node
}

type List struct {
	head *Node
	tail *Node
}

func NewList() *List {
	head := &Node{}
	tail := &Node{}
	head.next = tail
	tail.prev = head
	return &List{
		head: head,
		tail: tail,
	}
}

func (list *List) Remove(n *Node) {
	if n == nil {
		return
	}
	n.prev.next = n.next
	n.next.prev = n.prev
}

func (list *List) Push(n *Node) {
	n.prev = list.tail.prev
	n.next = list.tail
	list.tail.prev.next = n
	list.tail.prev = n
}

func (list *List) IsEmpty() bool {
	return list.head.next == list.tail
}

type LFUCache struct {
	m        map[int]*Node
	countMap map[int]*List // count -> list; 最旧访问的在前面，最近访问的在后面
	minF     int
	capacity int
}

func Constructor(capacity int) LFUCache {
	return LFUCache{
		m:        make(map[int]*Node),
		countMap: make(map[int]*List),
		capacity: capacity,
	}
}

func (this *LFUCache) Get(key int) int {
	if this.capacity == 0 {
		return -1
	}
	n := this.m[key]
	if n == nil {
		return -1
	}
	this.access(key)
	return n.val
}

func (this *LFUCache) Put(key int, value int) {
	if n := this.m[key]; n != nil {
		n.val = value
		this.access(key)
	} else {
		if len(this.m) == this.capacity {
			this.pop()
		}
		node := &Node{
			key: key,
			val: value,
		}
		this.m[key] = node
		this.minF = 1
		this.access(key)
	}
}

func (this *LFUCache) access(key int) {
	n := this.m[key]
	if this.countMap[n.count] != nil {
		this.countMap[n.count].Remove(n)
	}
	if this.countMap[n.count+1] == nil {
		this.countMap[n.count+1] = NewList()
	}
	this.countMap[n.count+1].Push(n)
	if n.count == this.minF && this.countMap[n.count].IsEmpty() {
		this.minF++
	}
	n.count++
}

func (this *LFUCache) pop() {
	list := this.countMap[this.minF]
	if !list.IsEmpty() {
		head := list.head.next
		list.Remove(head)
		delete(this.m, head.key)
	}
}

func main() {
	lFUCache := Constructor(2)
	lFUCache.Put(1, 1) // cache=[1,_], cnt(1)=1
	lFUCache.Put(2, 2) // cache=[2,1], cnt(2)=1, cnt(1)=1
	println(lFUCache.Get(1)) // 返回 1
	// cache=[1,2], cnt(2)=1, cnt(1)=2
	lFUCache.Put(3, 3) // 去除键 2 ，因为 cnt(2)=1 ，使用计数最小
	// cache=[3,1], cnt(3)=1, cnt(1)=2
	println(lFUCache.Get(2)) // 返回 -1（未找到）
	println(lFUCache.Get(3)) // 返回 3
	// cache=[3,1], cnt(3)=2, cnt(1)=2
	lFUCache.Put(4, 4) // 去除键 1 ，1 和 3 的 cnt 相同，但 1 最久未使用
	// cache=[4,3], cnt(4)=1, cnt(3)=2
	lFUCache.Get(1) // 返回 -1（未找到）
	lFUCache.Get(3) // 返回 3
	// cache=[3,4], cnt(4)=1, cnt(3)=3
	lFUCache.Get(4) // 返回 4
	// cache=[3,4], cnt(4)=2, cnt(3)=3

}
